package leetcode; /**
 * description:
 * author:张腾
 * date:2021-07-07
 */

/**
 * 给定一个由整数数组 A表示的环形数组 C，求 C的非空子数组的最大可能和。
 *
 * 在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length时C[i] = A[i]，且当i >= 0时C[i+A.length] = C[i]）
 *
 * 此外，子数组最多只能包含固定缓冲区 A中的每个元素一次。（形式上，对于子数组C[i], C[i+1], ..., C[j]，不存在i <= k1, k2 <= j其中k1 % A.length= k2 % A.length）
 */
public class leetcode918 {
    //环形子数组的最大和具有两种可能，一种是不使用环的情况，另一种是使用环的情况
    //不使用环的情况时，直接通过53题的思路，逐步求出整个数组中的最大子序和即可
    //【重点】使用到了环，则必定包含 A[n-1]和 A[0]两个元素且说明从A[1]到A[n-2]这个子数组中必定包含负数
    //【否则只通过一趟最大子序和就可以的=得出结果】
    //因此只需要把A[1]-A[n-2]间这些负数的最小和求出来
    //用整个数组的和 sum减掉这个负数最小和即可实现原环型数组的最大和
    //最后再比较直接通过53题思路求出无环子序列和用sum-min的有环子序列比较大小求出整个数组的最大值
    public int maxSubarraySumCircular(int[] A) {
        int dp = A[0];      //初始化
        int max = dp;                //最大子序列和
        int sum = dp;                //整个数组的和

//        求最大子序列和，见53题
        for (int i = 1; i < A.length; i++) {
            sum += A[i];
            dp = A[i] + Math.max(dp, 0);
            max = Math.max(dp, max);
        }

        int min = 0;
        dp = A[0];
        for (int i = 1; i < A.length - 1; i++) {
            dp = A[i] + Math.min(0, dp);
            min = Math.min(dp, min);
        }

        return Math.max(sum - min, max);
    }
}
